package list

object Test {
  def main(args: Array[String]): Unit = {
    val a = List(1, 2, 3)
    val b = List(4, 5, 6)
    val c = append(a, b)
    println(c)
    val s=msort((x:Int,y:Int)=>x<y)(List(2,5,6,3,7,9,1,0))
    println(s)
  }

  /**
    * 拼接两个同类型的list 相当于 :::
    * [T] 泛型
    *
    * @param a
    * @param b
    * @return
    */
  def append[T](a: List[T], b: List[T]): List[T] =
    a match {
      case Nil => b
      case a :: a1 => a :: append(a1, b);
    }

  /**
    * 归并排序
    *
    * @param less
    * @param xs
    * @tparam T
    * @return
    */
  def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {
    def merge(xs: List[T], ys: List[T]): List[T] = {
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
          // 两个list都非空
        case (x :: xs1, y :: ys1) =>
          if (less(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }
    }

    val n = xs.length / 2
    if (n == 0){
      println("return"+xs.toString())
      xs
    }
    else {
      val (ys, zs) = xs.splitAt(n)
      println("ys:"+ys.toString()+"===zs:"+zs.toString())
      merge(msort(less)(ys), msort(less)(zs))
    }
  }

}
